星尘

Go 并发编程-2.Mutex实现

发表于 更新于 分类于

初版 Mutex

“初版”的 Mutex 使用一个 flag 来表示锁是否被持有，实现比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// CAS操作，当时还没有抽象出atomic包
 func cas(val *int32, old, new int32) bool
 func semacquire(*int32)
 func semrelease(*int32)
 // 互斥锁的结构，包含两个字段
 type Mutex struct {
     key  int32 // 锁是否被持有的标识
     sema int32 // 信号量专用，用以阻塞/唤醒goroutine
 }
 
 // 保证成功在val上增加delta的值
 func xadd(val *int32, delta int32) (new int32) {
     for {
         v := *val
         if cas(val, v, v+delta) {
             return v + delta
         }
     }
     panic("unreached")
 }
 
 // 请求锁
 func (m *Mutex) Lock() {
     if xadd(&m.key, 1) == 1 { //标识加1，如果等于1，成功获取到锁
         return
     }
     semacquire(&m.sema) // 否则阻塞等待
 }
 
 func (m *Mutex) Unlock() {
     if xadd(&m.key, -1) == 0 { // 将标识减去1，如果等于0，则没有其它等待者
         return
     }
     semrelease(&m.sema) // 唤醒其它阻塞的goroutine
 }

CAS： CAS 指令将给定的值和一个内存地址中的值进行比较，如果它们是同一个值，就使用新值替换内存地址中的值，原子性保证这个指令总是基于最新的值进行计算，如果同时有其它线程已经修改了这个值，那么，CAS 会返回失败。

需要注意的是：Unlock 方法可以被任意的 goroutine 调用释放锁，即使是没持有这个互斥锁的 goroutine，也可以进行这个操作。这是因为，Mutex 本身并没有包含持有这把锁的 goroutine 的信息，所以，Unlock 也不会对此进行检查。Mutex 的这个设计一直保持至今。

第一次改进

1
2
3
4
5
6
7
8
9
10
11
12

type Mutex struct {
     state int32
     sema  uint32
 }


 const (
     mutexLocked = 1 << iota // mutex is locked
     mutexWoken
     mutexWaiterShift = iota
 )

虽然 Mutex 结构体还是包含两个字段，但是第一个字段已经改成了 state，它的含义也不一样了。

state 是一个复合型的字段，一个字段包含多个意义，这样可以通过尽可能少的内存来实现互斥锁。这个字段的第一位（最小的一位）来表示这个锁是否被持有，第二位代表是否有唤醒的 goroutine，剩余的位数代表的是等待此锁的 goroutine 数。

相对于初版的设计，这次的改动主要就是，新来的 goroutine 也有机会先获取到锁，甚至一个 goroutine 可能连续获取到锁，打破了先来先得的逻辑。

第二次改进

在 2015 年 2 月的改动中，如果新来的 goroutine 或者是被唤醒的 goroutine 首次获取不到锁，它们就会通过自旋（spin，通过循环不断尝试，spin 的逻辑是在runtime 实现的）的方式，尝试检查锁是否被释放。在尝试一定的自旋次数后，再执行原来的逻辑。

第三次改进

上述改进后新来的 goroutine 也参与竞争，有可能每次都会被新来的 goroutine 抢到获取锁的机会，在极端情况下，等待中的 goroutine 可能会一直获取不到锁，这就是饥饿问题。

跟之前的实现相比，当前的 Mutex 最重要的变化，就是增加饥饿模式。饥饿模式的最大等待时间阈值为 1 毫秒，这就意味着，一旦等待者等待的时间超过了这个阈值，Mutex 的处理就有可能进入饥饿模式，优先让等待者先获取到锁，新来的同学主动谦让一下，给老同志一些机会。

饥饿模式和正常模式

Mutex 可能处于两种操作模式下：正常模式和饥饿模式。

正常模式下，waiter 都是进入先入先出队列，被唤醒的 waiter 并不会直接持有锁，而是要和新来的 goroutine 进行竞争。新来的 goroutine 有先天的优势，它们正在 CPU 中运行，可能它们的数量还不少，所以，在高并发情况下，被唤醒的 waiter 可能比较悲剧地获取不到锁，这时，它会被插入到队列的前面。如果 waiter 获取不到锁的时间超过阈值 1 毫秒，那么，这个 Mutex 就进入到了饥饿模式。

在饥饿模式下，Mutex 的拥有者将直接把锁交给队列最前面的 waiter。新来的 goroutine 不会尝试获取锁，即使看起来锁没有被持有，它也不会去抢，也不会 spin，它会乖乖地加入到等待队列的尾部。

如果拥有 Mutex 的 waiter 发现下面两种情况的其中之一，它就会把这个 Mutex 转换成正常模式:

  • 此 waiter 已经是队列中的最后一个 waiter 了，没有其它的等待锁的 goroutine 了；
  • 此 waiter 的等待时间小于 1 毫秒。

理解go中的 mutex 的简单模式和饥饿模式？

在 Go 中，Mutex 是一种同步原语，用于防止竞争条件。当多个 Goroutine 将访问共享资源时，使用 Mutex 可以确保任何时刻只有一个 Goroutine 有权限访问该资源。

简单模式是指，在等待 Mutex 时，所有等待的 Goroutine 都会被放置在一个 FIFO 队列中，并按顺序获取 Mutex。这意味着先到达的 Goroutine 将首先获得 Mutex，而后到达的 Goroutine 则必须等待前面的 Goroutine 释放 Mutex 后才能获得它。这种方法可以确保每个 Goroutine 最终都能获得 Mutex，但可能导致一些 Goroutine 等待时间过长，从而导致饥饿。

饥饿模式是指，在等待 Mutex 时，某些 Goroutine 可能会无限期地等待，从而永远不能获得 Mutex。这种情况通常发生在高度竞争的情况下，其中一个或多个 Goroutine 不断尝试获得 Mutex，但总是被其他 Goroutine 所抢占。为了解决这个问题，Go 中的 Mutex 实现提供了一种饥饿模式，该模式可确保等待时间最长的 Goroutine 最终将获得 Mutex。这通过跟踪最后一次请求 Mutex 的时间来实现，然后在锁定时根据时间顺序授予 Mutex。

自旋是发生在简单模式中，还是饥饿模式中?

自旋通常是发生在简单模式中。在简单模式下，当 Goroutine 发现 Mutex 已经被其他 Goroutine 持有时，它会进入忙等待（自旋）状态，不断的检查 Mutex 是否已经释放。这种方式可以减少线程阻塞和切换的开销，但是如果多个 Goroutine 竞争同一 Mutex 的时候，会造成大量的 CPU 时间浪费。

在饥饿模式中，Mutex 会优先授予最久等待的 Goroutine，而不是让其他 Goroutine 不停地自旋等待。因此，在饥饿模式下，自旋不是主要的问题，而是可能会有一些 Goroutine 永远无法获得 Mutex，导致饥饿问题。

根据 state 字段的定义，计算等待一个 Mutex 的 goroutine 数最大是多少？

在 Go 中，Mutex 的结构体定义如下：

1
2
3
4
5
> Copy Codetype Mutex struct {
>     state int32
>     sema  uint32
> }
>

其中的 state 字段是一个 32 位的有符号整数，表示 Mutex 的状态。具体来说，低 31 位用于计数器，并且最高位用于指示 Mutex 是否被锁定。

因此，在理论上，等待一个 Mutex 的 Goroutine 数的最大值应该是 (1<<31)-1，即 2147483647，这是由于 Mutex 计数器使用了 31 位二进制数，所以可以支持的最大整数值为 2^31-1。

不过，需要注意的是，实际情况中等待 Mutex 的 Goroutine 数可能会受到其他因素的限制，例如系统硬件、操作系统调度策略、Goroutine 的性质和访问共享资源的模式等因素，因此，实际上能够同时等待 Mutex 的 Goroutine 数量很少会达到这个最大值。

没有理解 “低 31 位用于计数器，并且最高位用于指示 Mutex 是否被锁定。” 可以画个图解释下吗？

当我们说“低31位用于计数器”时，意味着一个32位的二进制数的前31位（即最右边的31个位）将被用作计数器。这个计数器可以存储任何数字从0到2^31-1（因为每一位都可以是0或1，所以有2的31次方种可能性）。

现在，考虑到这个32位二进制数的最高位（即最左边的一位）。这个位被称为“符号位”，其值可以为0或1。在这种情况下，我们使用它来表示Mutex是否被锁定。如果最高位为0，则Mutex未被锁定；如果最高位为1，则Mutex被锁定。

下面是一个示意图，说明了32位的二进制数是如何被使用来实现Mutex的：

1
2
3
4
5
6
7
8
9
10
>   31       1
>    |       |
>    +-------+
>    |Mutex  |
>    |Locked |
>    |Bit    |
>    +-------+
>    |Counter|
>    +-------+
>

如上图所示，最高位的位被用作Mutex锁定标志。余下的31位被用作计数器，记录Mutex被锁定的次数。在实现Mutex时，每当Mutex被锁定时，计数器会递增。当Mutex被解锁时，计数器会递减。